package rank;

import com.alibaba.fastjson.JSON;

/**
 * Created by zhangyanfei on 2018/1/3.
 *
 * @author zhangyanfei
 * @date 2018/01/03
 */
public class BaseSort {

    /**
     * 冒泡排序
     * 两两比较，较小的上升
     *
     * @param array
     */
    public static void bublingSort(int[] array) {
        System.out.println("初始值：" + JSON.toJSONString(array));
        for (int j = 0; j < array.length - 1; j++) {
            for (int i = 0; i < array.length - 1 - j; i++) {
                if (array[i] < array[i + 1]) {
                    array[i] = array[i] + array[i + 1];
                    array[i + 1] = array[i] - array[i + 1];
                    array[i] = array[i] - array[i + 1];
                }
            }
            System.out.println("第" + (j + 1) + "次：" + JSON.toJSONString(array));
        }
    }

    /**
     * 第一个数和后面每一个数比较
     *
     * @param array
     */
    public static void exchangeSort(int[] array) {
        System.out.println("初始值：" + JSON.toJSONString(array));
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    array[i] = array[i] + array[j];
                    array[j] = array[i] - array[j];
                    array[i] = array[i] - array[j];
                }
            }
            System.out.println("第" + (i + 1) + "次：" + JSON.toJSONString(array));
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 1, 4, 7, 6, 2, 8};
        System.out.println("冒泡排序");
        bublingSort(array);
        System.out.println("交换排序");
        exchangeSort(array);
        System.out.println("插入排序");
        insertSort(array);
        System.out.println("选择排序");
        chooseSort(array);
        System.out.println("希尔排序");
        shellSort(array);
    }

    /**
     * 中值排序
     *
     * @param array
     */
    public static void middleSort(int[] array) {

    }

    /**
     * 插入排序
     * 每次取一个值 往有序列表里面插入
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        System.out.println("初始值：" + JSON.toJSONString(array));
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (array[j] > array[j - 1]) {
                    array[j] = array[j] + array[j - 1];
                    array[j - 1] = array[j] - array[j - 1];
                    array[j] = array[j] - array[j - 1];
                }
            }
            System.out.println("第" + (i + 1) + "次：" + JSON.toJSONString(array));
        }
    }

    /**
     * 选择排序
     * 选择最小或者最大 交换
     *
     * @param array
     */
    public static void chooseSort(int[] array) {
        System.out.println("初始值：" + JSON.toJSONString(array));
        for (int i = 0; i < array.length - 1; i++) {
            int min = array[i];
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (min > array[j]) {
                    min = array[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                array[i] = array[i] + array[minIndex];
                array[minIndex] = array[i] - array[minIndex];
                array[i] = array[i] - array[minIndex];
            }
            System.out.println("第" + (i + 1) + "次：" + JSON.toJSONString(array));
        }
    }

    /**
     * 希尔插入排序
     * 分片插入
     * 固定步长
     * @param array
     */
    public static void shellSort(int[] array) {
        int length = array.length;
        int gap = length / 2;
        while (gap != 0) {
            System.out.println("初始值：" + JSON.toJSONString(array));
            for (int i = gap; i < length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (array[j] < array[j + gap]) {
                        array[j] = array[j] + array[j + gap];
                        array[j + gap] = array[j] - array[j + gap];
                        array[j] = array[j] - array[j + gap];
                    }
                }
                System.out.println("第" + (i - gap + 1) + "次：" + JSON.toJSONString(array));
            }
            gap = gap / 2;
        }
    }
}
